SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Overlap–save method</title>

</head>

Overlap–save method

</h1>

</header>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr">In <a href="Signal_processing" title="Signal processing">signal processing</a>, overlap–save is the traditional name for an efficient way to evaluate the <a href="Convolution#Discrete_convolution" title="Convolution">discrete convolution</a> between a very long signal <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x[n]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x[n]}</annotation>

</semantics>

</math><img src="./864cbbefbdcb55af4d9390911de1bf70167c4a3d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.018ex; height:2.843ex;" alt="{\displaystyle x[n]}" loading="lazy"> and a <a href="Finite_impulse_response" title="Finite impulse response">finite impulse response</a> (FIR) filter <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h[n]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h[n]}</annotation>

</semantics>

</math><img src="./89981bbbb05ffd469eeadb828c18359965985e46.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.027ex; height:2.843ex;" alt="{\displaystyle h[n]}" loading="lazy">:

/* start https://en.wikipedia.org/ */

.mw-parser-output table.numblk{border-collapse:collapse;border:none;margin-top:0;margin-right:0;margin-bottom:0}.mw-parser-output table.numblk>tbody>tr>td{vertical-align:middle;padding:0}.mw-parser-output table.numblk>tbody>tr>td:nth-child(2){width:99%}.mw-parser-output table.numblk>tbody>tr>td:nth-child(2)>table{border-collapse:collapse;margin:0;border:none;width:100%}.mw-parser-output table.numblk>tbody>tr>td:nth-child(2)>table>tbody>tr:first-child>td:first-child,.mw-parser-output table.numblk>tbody>tr>td:nth-child(2)>table>tbody>tr:first-child>td:last-child{padding:0 0.4ex}.mw-parser-output table.numblk>tbody>tr>td:nth-child(2)>table>tbody>tr:first-child>td:nth-child(2){width:100%;padding:0}.mw-parser-output table.numblk>tbody>tr>td:nth-child(2)>table>tbody>tr:last-child>td{padding:0}.mw-parser-output table.numblk>tbody>tr>td:last-child{font-weight:bold}.mw-parser-output table.numblk.numblk-raw-n>tbody>tr>td:last-child{font-weight:unset}.mw-parser-output table.numblk>tbody>tr>td:last-child::before{content:"("}.mw-parser-output table.numblk>tbody>tr>td:last-child::after{content:")"}.mw-parser-output table.numblk.numblk-raw-n>tbody>tr>td:last-child::before,.mw-parser-output table.numblk.numblk-raw-n>tbody>tr>td:last-child::after{content:none}.mw-parser-output table.numblk>tbody>tr>td{border:none}.mw-parser-output table.numblk.numblk-border>tbody>tr>td{border:thin solid}.mw-parser-output table.numblk>tbody>tr>td:nth-child(2)>table>tbody>tr:first-child>td{border:none}.mw-parser-output table.numblk.numblk-border>tbody>tr>td:nth-child(2)>table>tbody>tr:first-child>td{border:thin solid}.mw-parser-output table.numblk>tbody>tr>td:nth-child(2)>table>tbody>tr:last-child>td{border-left:none;border-right:none;border-bottom:none}.mw-parser-output table.numblk.numblk-border>tbody>tr>td:nth-child(2)>table>tbody>tr:last-child>td{border-left:thin solid;border-right:thin solid;border-bottom:thin solid}.mw-parser-output table.numblk:target{color:var(--color-base,#202122);background-color:#cfe8fd}@media screen{html.skin-theme-clientpref-night .mw-parser-output table.numblk:target{color:var(--color-base,#eaecf0);background-color:#301702}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output table.numblk:target{color:var(--color-base,#eaecf0);background-color:#301702}}

/* end https://en.wikipedia.org/ */

</style><table role="presentation" class="numblk" style="margin-left: 1.6em;"><tbody><tr><td class="nowrap"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y[n]=x[n]*h[n]\ \triangleq \ \sum _{m=-\infty }^{\infty }h[m]\cdot x[n-m]=\sum _{m=1}^{M}h[m]\cdot x[n-m],}">

</mrow>

</mrow>

</munderover>

</mrow>

</mrow>

</munderover>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y[n]=x[n]*h[n]\ \triangleq \ \sum _{m=-\infty }^{\infty }h[m]\cdot x[n-m]=\sum _{m=1}^{M}h[m]\cdot x[n-m],}</annotation>

</semantics>

</math><img src="./6c695304cee4b4c978397073ba487fb5b5f97686.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:66.037ex; height:7.343ex;" alt="{\displaystyle y[n]=x[n]*h[n]\ \triangleq \ \sum _{m=-\infty }^{\infty }h[m]\cdot x[n-m]=\sum _{m=1}^{M}h[m]\cdot x[n-m],}" loading="lazy">

</td> <td></td> <td class="nowrap">Eq.1</td></tr></tbody></table>

</div>

where h[m] = 0 for m outside the region [1, M].

This article uses common abstract notations, such as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle y(t)=x(t)*h(t),}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle y(t)=x(t)*h(t),}</annotation>

</semantics>

</math><img src="./a1a31c01ec86e6295c78878fadee5277058e561f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.711ex; height:2.843ex;" alt="{\textstyle y(t)=x(t)*h(t),}" loading="lazy"> or <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle y(t)={\mathcal {H}}\{x(t)\},}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle y(t)={\mathcal {H}}\{x(t)\},}</annotation>

</semantics>

</math><img src="./82b2eac7eb622278e2fae3321f6b622bd8593ec5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.817ex; height:2.843ex;" alt="{\textstyle y(t)={\mathcal {H}}\{x(t)\},}" loading="lazy"> in which it is understood that the functions should be thought of in their totality, rather than at specific instants <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle t}</annotation>

</semantics>

</math><img src="./b2bc926f90178739fccd01a96c6fa778ab3535d6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\textstyle t}" loading="lazy"> (see <a href="Convolution#Notation" title="Convolution">Convolution#Notation</a>).

The concept is to compute short segments of y[n] of an arbitrary length L, and concatenate the segments together. That requires longer input segments that overlap the next input segment. The overlapped data gets "saved" and used a second time.<a href="#cite_note-OLA-2">[1]</a> First we describe that process with just conventional convolution for each output segment. Then we describe how to replace that convolution with a more efficient method.

Consider a segment that begins at n = kL + M, for any integer k, and define:

<msub>

</mrow>

</msub>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

<mtext>otherwise</mtext>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{k}[n]\ \triangleq {\begin{cases}x[n+kL],&1\leq n\leq L+M-1\\0,&{\textrm {otherwise}}.\end{cases}}}</annotation>

</semantics>

</math><img src="./86d96799af4ad7297c6e47260666c2a4e4ef20a3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:43.525ex; height:6.176ex;" alt="{\displaystyle x_{k}[n]\ \triangleq {\begin{cases}x[n+kL],&1\leq n\leq L+M-1\\0,&{\textrm {otherwise}}.\end{cases}}}" loading="lazy"></dd></dl>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{k}[n]\ \triangleq \ x_{k}[n]*h[n]=\sum _{m=1}^{M}h[m]\cdot x_{k}[n-m].}</annotation>

</semantics>

</math><img src="./8fd9d2fd0bbbfdd29588f4269fa83eb6a5c6bb78.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:44.52ex; height:7.343ex;" alt="{\displaystyle y_{k}[n]\ \triangleq \ x_{k}[n]*h[n]=\sum _{m=1}^{M}h[m]\cdot x_{k}[n-m].}" loading="lazy"></dd></dl>

Then, for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle kL+M+1\leq n\leq kL+L+M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle kL+M+1\leq n\leq kL+L+M}</annotation>

</semantics>

</math><img src="./5a09aa10ec5f44fdf137ffcd9b106c36b7b1c9b5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:32.171ex; height:2.343ex;" alt="{\displaystyle kL+M+1\leq n\leq kL+L+M}" loading="lazy">, and equivalently <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M+1\leq n-kL\leq L+M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M+1\leq n-kL\leq L+M}</annotation>

</semantics>

</math><img src="./e61429620e46a607aaf33d1dd4dd39295d30c199.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:26.537ex; height:2.343ex;" alt="{\displaystyle M+1\leq n-kL\leq L+M}" loading="lazy">, we can write:

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y[n]=\sum _{m=1}^{M}h[m]\cdot x_{k}[n-kL-m]\ \ \triangleq \ \ y_{k}[n-kL].}</annotation>

</semantics>

</math><img src="./a7c079ad24edca1c7175376f25063e1a0b6e3c26.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:49.466ex; height:7.343ex;" alt="{\displaystyle y[n]=\sum _{m=1}^{M}h[m]\cdot x_{k}[n-kL-m]\ \ \triangleq \ \ y_{k}[n-kL].}" loading="lazy"></dd></dl>

With the substitution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j=n-kL}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j=n-kL}</annotation>

</semantics>

</math><img src="./96c03540f0adca4d92f1d1461b761e9ca2c3da01.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:11.112ex; height:2.509ex;" alt="{\displaystyle j=n-kL}" loading="lazy">, the task is reduced to computing <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{k}[j]}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{k}[j]}</annotation>

</semantics>

</math><img src="./594a6b04e674505684013555e4e89ff0bcfe02ae.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.48ex; height:2.843ex;" alt="{\displaystyle y_{k}[j]}" loading="lazy"> for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M+1\leq j\leq L+M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M+1\leq j\leq L+M}</annotation>

</semantics>

</math><img src="./07a7f315f14c7fbf93f87c29ff44d2e19f289438.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:20.465ex; height:2.509ex;" alt="{\displaystyle M+1\leq j\leq L+M}" loading="lazy">. These steps are illustrated in the first 3 traces of Figure 1, except that the desired portion of the output (third trace) corresponds to 1  ≤  j  ≤  L.<a href="#cite_note-3">[B]</a>

If we periodically extend xk[n] with period N  ≥  L + M − 1, according to:

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{k,N}[n]\ \triangleq \ \sum _{\ell =-\infty }^{\infty }x_{k}[n-\ell N],}</annotation>

</semantics>

</math><img src="./5d47dd2d227e66f4bfcefd7e64a245876fb0f04e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:28.571ex; height:7.009ex;" alt="{\displaystyle x_{k,N}[n]\ \triangleq \ \sum _{\ell =-\infty }^{\infty }x_{k}[n-\ell N],}" loading="lazy"></dd></dl>

the convolutions  <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x_{k,N})*h\,}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x_{k,N})*h\,}</annotation>

</semantics>

</math><img src="./729da9273bdd899edd8d3e36412efea7267a26ec.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:10.065ex; height:3.009ex;" alt="{\displaystyle (x_{k,N})*h\,}" loading="lazy">  and  <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{k}*h\,}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{k}*h\,}</annotation>

</semantics>

</math><img src="./3c581b90cc2708e3b96254401f12c54873570eeb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.339ex; height:2.509ex;" alt="{\displaystyle x_{k}*h\,}" loading="lazy">  are equivalent in the region <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M+1\leq n\leq L+M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M+1\leq n\leq L+M}</annotation>

</semantics>

</math><img src="./a10053d84e43c53dd95c81d9d6b173e22e453de8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:20.902ex; height:2.343ex;" alt="{\displaystyle M+1\leq n\leq L+M}" loading="lazy">. It is therefore sufficient to compute the N-point <a href="Circular_convolution" title="Circular convolution">circular (or cyclic) convolution</a> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{k}[n]\,}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{k}[n]\,}</annotation>

</semantics>

</math><img src="./dc9d9200977fc896075d42002a94bfb133d0dd0a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.494ex; height:2.843ex;" alt="{\displaystyle x_{k}[n]\,}" loading="lazy"> with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h[n]\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h[n]\,}</annotation>

</semantics>

</math><img src="./657f337326ef0221b43c4ae709e54fe608a6a527.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.414ex; height:2.843ex;" alt="{\displaystyle h[n]\,}" loading="lazy">  in the region [1, N].  The subregion [M + 1, L + M] is appended to the output stream, and the other values are discarded.  The advantage is that the circular convolution can be computed more efficiently than linear convolution, according to the <a href="Discrete_Fourier_transform#Circular_convolution_theorem_and_cross-correlation_theorem" title="Discrete Fourier transform">circular convolution theorem</a>:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{k}[n]\ =\ \scriptstyle {\text{IDFT}}_{N}\displaystyle (\ \scriptstyle {\text{DFT}}_{N}\displaystyle (x_{k}[n])\cdot \ \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n])\ ),}</annotation>

</semantics>

</math><img src="./ee068be99a264a0051a5a36497df695897bebf42.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:42.993ex; height:2.843ex;" alt="{\displaystyle y_{k}[n]\ =\ \scriptstyle {\text{IDFT}}_{N}\displaystyle (\ \scriptstyle {\text{DFT}}_{N}\displaystyle (x_{k}[n])\cdot \ \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n])\ ),}" loading="lazy">

</td> <td></td> <td class="nowrap">Eq.2</td></tr></tbody></table>

</div>

where:

<ul><li>DFTN and IDFTN refer to the <a href="Discrete_Fourier_transform" title="Discrete Fourier transform">Discrete Fourier transform</a> and its inverse, evaluated over N discrete points, and</li>

<li>L is customarily chosen such that N = L+M-1 is an integer power-of-2, and the transforms are implemented with the <a href="Fast_Fourier_transform" title="Fast Fourier transform">FFT</a> algorithm, for efficiency.</li>

<li>The leading and trailing edge-effects of circular convolution are overlapped and added,<a href="#cite_note-4">[C]</a> and subsequently discarded.<a href="#cite_note-5">[D]</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Pseudocode">Pseudocode</h2></div>

<pre>(Overlap-save algorithm for linear convolution)

h = FIR_impulse_response

M = length(h)

overlap = M − 1

N = 8 × overlap (see next section for a better choice)

step_size = N − overlap

H = DFT(h, N)

position = 0

while position + N ≤ length(x)

yt = IDFT(DFT(x(position+(1:N))) × H)

y(position+(1:step_size)) = yt(M : N) (discard M−1 y-values)

position = position + step_size

end

</pre>

<div class="mw-heading mw-heading2"><h2 id="Efficiency_considerations">Efficiency considerations</h2></div>

When the DFT and IDFT are implemented by the FFT algorithm, the pseudocode above requires about N (log2(N) + 1) complex multiplications for the FFT, product of arrays, and IFFT.<a href="#cite_note-6">[E]</a> Each iteration produces N-M+1 output samples, so the number of complex multiplications per output sample is about:

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {N(\log _{2}(N)+1)}{N-M+1}}.\,}</annotation>

</semantics>

</math><img src="./ffa1e74e4c1fe39a81cd381714644348397e608a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:17.645ex; height:5.843ex;" alt="{\displaystyle {\frac {N(\log _{2}(N)+1)}{N-M+1}}.\,}" loading="lazy">

</td> <td></td> <td class="nowrap">Eq.3</td></tr></tbody></table>

</div>

For example, when <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M=201}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M=201}</annotation>

</semantics>

</math><img src="./4504268e9ece838cb5adba7972e7abf534b27aed.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.028ex; height:2.176ex;" alt="{\displaystyle M=201}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N=1024,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N=1024,}</annotation>

</semantics>

</math><img src="./6726a953a70c376f15978b353ae976c23e0937e9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.459ex; height:2.509ex;" alt="{\displaystyle N=1024,}" loading="lazy"> <a href="#math_Eq.3">Eq.3</a> equals <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 13.67,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 13.67,}</annotation>

</semantics>

</math><img src="./0e842cb8e9b005740aa5e0b2dbb963a588c43538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.944ex; height:2.509ex;" alt="{\displaystyle 13.67,}" loading="lazy"> whereas direct evaluation of <a href="#math_Eq.1">Eq.1</a> would require up to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 201}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 201}</annotation>

</semantics>

</math><img src="./278d5f2c7e980de648903c802691b67116dced05.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.487ex; height:2.176ex;" alt="{\displaystyle 201}" loading="lazy"> complex multiplications per output sample, the worst case being when both <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h}</annotation>

</semantics>

</math><img src="./b26be3e694314bc90c3215047e4a2010c6ee184a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.339ex; height:2.176ex;" alt="{\displaystyle h}" loading="lazy"> are complex-valued. Also note that for any given <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M,}</annotation>

</semantics>

</math><img src="./b466e90209f39c0c2caad1b11445824b82c2f536.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.089ex; height:2.509ex;" alt="{\displaystyle M,}" loading="lazy"> <a href="#math_Eq.3">Eq.3</a> has a minimum with respect to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N.}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N.}</annotation>

</semantics>

</math><img src="./356b8b60a047de347b447f2bdafaaccf47502031.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.71ex; height:2.176ex;" alt="{\displaystyle N.}" loading="lazy"> Figure 2 is a graph of the values of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> that minimize <a href="#math_Eq.3">Eq.3</a> for a range of filter lengths (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy">).

Instead of <a href="#math_Eq.1">Eq.1</a>, we can also consider applying <a href="#math_Eq.2">Eq.2</a> to a long sequence of length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N_{x}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{x}}</annotation>

</semantics>

</math><img src="./c1eb9520e339a292309b68edc1466f4e90113ddf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.039ex; height:2.509ex;" alt="{\displaystyle N_{x}}" loading="lazy"> samples. The total number of complex multiplications would be:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{x}\cdot (\log _{2}(N_{x})+1).}</annotation>

</semantics>

</math><img src="./01cf7d19cf2f40bdf8695dd6665573b8507aa7a0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.051ex; height:2.843ex;" alt="{\displaystyle N_{x}\cdot (\log _{2}(N_{x})+1).}" loading="lazy"></dd></dl>

Comparatively, the number of complex multiplications required by the pseudocode algorithm is:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{x}\cdot (\log _{2}(N)+1)\cdot {\frac {N}{N-M+1}}.}</annotation>

</semantics>

</math><img src="./49d6dbf38cf993cdffa7c90309cdf2ce09dc94d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:32.94ex; height:5.343ex;" alt="{\displaystyle N_{x}\cdot (\log _{2}(N)+1)\cdot {\frac {N}{N-M+1}}.}" loading="lazy"></dd></dl>

Hence the cost of the overlap–save method scales almost as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O\left(N_{x}\log _{2}N\right)}">

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O\left(N_{x}\log _{2}N\right)}</annotation>

</semantics>

</math><img src="./ad984eaa7ac7c1a0d3a90d6ffb33a54b6d436533.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.872ex; height:2.843ex;" alt="{\displaystyle O\left(N_{x}\log _{2}N\right)}" loading="lazy"> while the cost of a single, large circular convolution is almost <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O\left(N_{x}\log _{2}N_{x}\right)}">

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O\left(N_{x}\log _{2}N_{x}\right)}</annotation>

</semantics>

</math><img src="./7059fd526359ba05edfa9289f3faf83b778a4a7c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.847ex; height:2.843ex;" alt="{\displaystyle O\left(N_{x}\log _{2}N_{x}\right)}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Overlap–discard">Overlap–discard</h2></div>

Overlap–discard<a href="#cite_note-f.harris-7">[2]</a> and Overlap–scrap<a href="#cite_note-Frerking-8">[3]</a> are less commonly used labels for the same method described here. However, these labels are actually better (than overlap–save) to distinguish from <a href="Overlap%E2%80%93add_method" title="Overlap–add method">overlap–add</a>, because both methods "save", but only one discards. "Save" merely refers to the fact that M − 1 input (or output) samples from segment k are needed to process segment k + 1.

<div class="mw-heading mw-heading3"><h3 id="Extending_overlap–save">Extending overlap–save</h3></div>

The overlap–save algorithm can be extended to include other common operations of a system:<a href="#cite_note-9">[F]</a><a href="#cite_note-Borgerding-10">[4]</a>

<ul><li>additional IFFT channels can be processed more cheaply than the first by reusing the forward FFT</li>

<li>sampling rates can be changed by using different sized forward and inverse FFTs</li>

<li>frequency translation (mixing) can be accomplished by rearranging frequency bins</li></ul>

<ul><li><a href="Overlap%E2%80%93add_method" title="Overlap–add method">Overlap–add method</a></li>

<li><a href="Circular_convolution#Example" title="Circular convolution">Circular convolution#Example</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-upper-alpha">

<li id="cite_note-1"><a href="#cite_ref-1">^</a> <a href="#refRabiner">Rabiner and Gold</a>, Fig 2.35, fourth trace.

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> Shifting the undesirable edge effects to the last M-1 outputs is a potential run-time convenience, because the IDFT can be computed in the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y[n]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y[n]}</annotation>

</semantics>

</math><img src="./305428e6d1fb59cd0163a7a96ace52292a262afa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.844ex; height:2.843ex;" alt="{\displaystyle y[n]}" loading="lazy"> buffer, instead of being computed and copied. Then the edge effects can be overwritten by the next IDFT.  A subsequent footnote explains how the shift is done, by a time-shift of the impulse response.

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> Not to be confused with the <a href="Overlap-add_method" class="mw-redirect" title="Overlap-add method">Overlap-add method</a>, which preserves separate leading and trailing edge-effects.

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> The edge effects can be moved from the front to the back of the IDFT output by replacing <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n])}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n])}</annotation>

</semantics>

</math><img src="./c8b62f1e3076cbb889d1f75935625152f54260c7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.701ex; height:2.843ex;" alt="{\displaystyle \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n])}" loading="lazy"> with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1])=\ \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1-N]),}">

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1])=\ \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1-N]),}</annotation>

</semantics>

</math><img src="./4d183616f0965f41fa1094f723772164c57bc814.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:49.203ex; height:2.843ex;" alt="{\displaystyle \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1])=\ \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1-N]),}" loading="lazy"> meaning that the N-length buffer is circularly-shifted (rotated) by M-1 samples. Thus the h(M) element is at n=1. The h(M-1) element is at n=N. h(M-2) is at n=N-1. Etc.

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> Cooley–Tukey FFT algorithm for N=2k needs (N/2) log2(N) – see <a href="Fast_Fourier_transform#Definition" title="Fast Fourier transform">FFT – Definition and speed</a>

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <a href="#refCarlin">Carlin et al. 1999</a>, p 31, col 20.

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.dsprelated.com/freebooks/sasp/Overlap_Add_OLA_STFT_Processing.html">"Overlap-Add (OLA) STFT Processing | Spectral Audio Signal Processing"</a>. www.dsprelated.com. Retrieved 2024-03-02. <q>The name overlap-save comes from the fact that L-1 samples of the previous frame [here: M-1 samples of the current frame] are saved for computing the next frame.</q></cite>

</li>

<cite id="CITEREFHarris,_F.J.1987" class="citation book cs1">Harris, F.J. (1987). D.F.Elliot (ed.). Handbook of Digital Signal Processing. San Diego: Academic Press. pp. 633–699. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0122370759</bdi>.</cite>

</li>

<cite id="CITEREFFrerking,_Marvin1994" class="citation book cs1">Frerking, Marvin (1994). Digital Signal Processing in Communication Systems. New York: Van Nostrand Reinhold. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0442016166</bdi>.</cite>

</li>

<cite id="CITEREFBorgerding2006" class="citation journal cs1">Borgerding, Mark (2006). <a rel="nofollow" class="external text" href="https://ieeexplore.ieee.org/document/1598092">"Turning Overlap–Save into a Multiband Mixing, Downsampling Filter Bank"</a>. IEEE Signal Processing Magazine. 23 (March 2006): 158–161. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FMSP.2006.1598092">10.1109/MSP.2006.1598092</a>.</cite>

</li>

</ol></div></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .refbegin{margin-bottom:0.5em}.mw-parser-output .refbegin-hanging-indents>ul{margin-left:0}.mw-parser-output .refbegin-hanging-indents>ul>li{margin-left:0;padding-left:3.2em;text-indent:-3.2em}.mw-parser-output .refbegin-hanging-indents ul,.mw-parser-output .refbegin-hanging-indents ul li{list-style:none}@media(max-width:720px){.mw-parser-output .refbegin-hanging-indents>ul>li{padding-left:1.6em;text-indent:-1.6em}}.mw-parser-output .refbegin-columns{margin-top:0.3em}.mw-parser-output .refbegin-columns ul{margin-top:0}.mw-parser-output .refbegin-columns li{page-break-inside:avoid;break-inside:avoid-column}@media screen{.mw-parser-output .refbegin{font-size:90%}}

/* end https://en.wikipedia.org/ */

</style><div class="refbegin" style="">

<ol><li value="4"><cite id="refRabiner" class="citation book cs1">Rabiner, Lawrence R.; Gold, Bernard (1975). <a rel="nofollow" class="external text" href="https://archive.org/details/theoryapplicatio00rabi/page/67">"2.25"</a>. Theory and application of digital signal processing. Englewood Cliffs, N.J.: Prentice-Hall. pp. <a rel="nofollow" class="external text" href="https://archive.org/details/theoryapplicatio00rabi/page/63">63–67</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-13-914101-4</bdi>.</cite></li>

/* start https://en.wikipedia.org/ */

.mw-parser-output .citation{word-wrap:break-word}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}

/* end https://en.wikipedia.org/ */

</style><a rel="nofollow" class="external text" href="https://worldwide.espacenet.com/textdoc?DB=EPODOC&IDX=US6898235">US patent 6898235</a>, Carlin, Joe; Collins, Terry & Hays, Peter et al., "Wideband communication intercept and direction finding device using hyperchannelization", published 1999-12-10, issued 2005-05-24<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Apatent&rft.number=6898235&rft.cc=US&rft.title=Wideband+communication+intercept+and+direction+finding+device+using+hyperchannelization&rft.inventor=Carlin%2C+Joe&rft.date=2005-05-24&rft.appldate=1999-12-10&rft.pubdate=1999-12-10"> , also available at <a rel="nofollow" class="external free" href="https://patentimages.storage.googleapis.com/4d/39/2a/cec2ae6f33c1e7/US6898235.pdf">https://patentimages.storage.googleapis.com/4d/39/2a/cec2ae6f33c1e7/US6898235.pdf</a></li></ol>

</div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li>Dr. Deepa Kundur, <a rel="nofollow" class="external text" href="https://www.comm.utoronto.ca/~dkundur/course_info/real-time-DSP/notes/8_Kundur_Overlap_Save_Add.pdf">Overlap Add and Overlap Save</a>, University of Toronto</li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-05-26" href="https://en.wikipedia.org/wiki/?title=Overlap%E2%80%93save_method&oldid=1292286621">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>